package src.string;

public class no560 {  //和为 K 的子数组
    public static void main(String[] args) {
        int[] arr ={1, -1, 0};
        System.out.println(subarraySum(arr, 0));
    }

    //法1：暴力枚举
    public static int subarraySum(int[] nums, int k) {

        int count = 0;

        for(int left = 0; left < nums.length; left++) {
            int sum = 0;
            for(int right = left; right < nums.length; right++) {
                sum += nums[right];
                if(sum == k) {
                    count++;
                }
            }
        }

        return count;

    }

    //法2：前缀和
    //谨记：数组不是单调的话，不要用滑动窗口，考虑用前缀和
    public int subarraySum2(int[] nums, int k) {
        int len = nums.length;
        // 计算前缀和数组
        int[] preSum = new int[len + 1];
        preSum[0] = 0;
        for (int i = 0; i < len; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }

        int count = 0;
        for (int left = 0; left < len; left++) {
            for (int right = left; right < len; right++) {
                // 区间和 [left..right]，注意下标偏移
                if (preSum[right + 1] - preSum[left] == k) {
                    count++;
                }
            }
        }
        return count;
    }
    /**
     * 1 2 2 3
     * 1 3 5 8
     */
}
